
package binary_tree;

import java.io.*;
import java.util.*;

class Node {
    public int id;
    public String value;
    public Node leftChild;
    public Node rightChild;
    Node(int id, String value){
        this.id = id;
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }
}

class Tree {
    public Node root;

    public Tree() {
        root = null;
    }

    public Node returnRoot() {
        return root;
    }

    public void insert(String[] value) {
        Node newNode = new Node(Integer.parseInt(value[0]), value[1]);
        System.out.println(newNode.id + newNode.value);
        if (root == null)
            root = newNode;
        else {
            int findId = newNode.id / 2;
            Node tem = searchNode(root, findId);
            if (newNode.id % 2 == 0)
                tem.leftChild = newNode;
            else
                tem.rightChild = newNode;
        }
    }

    private Node searchNode(Node root, int value) {
        if (root.id == value)
            return root;
        if (root == null)
            return null;

        Node result = null;
        // TÃ¬m trÃªn nhÃ¡nh con bÃªn trÃ¡i
        result = searchNode(root.leftChild, value);
        // TÃ¬m trÃªn nhÃ¡nh con bÃªn pháº£i
        if (result == null)
            result = searchNode(root.rightChild, value);
        return result;
    }

    public void inOrder(Node Root) {
        if (Root != null) {
            inOrder(Root.leftChild);
            System.out.print(Root.value);
            inOrder(Root.rightChild);
        }
    }
}

public class Solution {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("test_input.txt"));
        Scanner sc = new Scanner(System.in);
        int value;
        Tree theTree = new Tree();
        for (int test_case = 1; test_case <= 2; test_case++) {
            int N = Integer.parseInt(sc.nextLine());
            for (int i = 1; i <= N; i++) {
                String[] s = sc.nextLine().split(" ");
                theTree.insert(s);
            }

            System.out.print("#" + test_case + " ");
            theTree.inOrder(theTree.returnRoot());
            System.out.println();
        }

    }
}
